Not applicable.
Not applicable.
Wireless communication networks have significant application in permitting communication between various types of mobile apparatus, referred to herein as nodes. One such growing application is in tactical military environments in which the network is subject to rapid changes by which nodes are added, removed or moved from one location to another within the network. Such dynamically changing wireless networks are sometimes referred to as wireless ad hoc networks and include nodes which are able to communicate with each other over a wireless media, without any infrastructure, or wired network. Illustrative nodes include cellular telephones and portable computers which communicate by transmitting and receiving radio frequency (RF) signals in the form of packets.
Desirable characteristics of wireless ad hoc networks include the ability to adapt to frequent and rapid changes in node connections, compatibility with the Internet Protocol (IP) and other network protocols, and the ability to provide reliable communication. It is further desirable that the bandwidth necessary to establish and maintain the wireless ad hoc network not be excessive in order to permit a high data throughput and conserve node battery power.
In general, each network node maintains a routing table containing one or more routes to every other node in the network. Routing tables may be updated periodically or in response to detection of a change in the network. Various techniques are used to update routing tables. One such technique requires that each network node broadcast a routing message to every other network node, thereby permitting each node to learn the identity and connectivity of every other network node and, with that information, determine one or more optimal routes to each such node. However, such a broadcast-based approach requires significant bandwidth and thus, reduces data throughput.
In many wireless networks, every network node is capable of receiving packets from a source node and forwarding packets to a destination node. However, in some wireless ad hoc networks, only selected nodes are designated as xe2x80x9cbackbone nodesxe2x80x9d and provide a fully connected packet forwarding infrastructure responsible for forwarding packets from a source node to a destination node, while the remaining network nodes are able to use the network (i.e., send and receive packets), but do not forward packets from a source node to a destination node. Such networks strike a balance between designating as backbone nodes the fewest number of nodes necessary to fully connect the network in order to increase bandwidth efficiency by reducing overhead and competition for channel capacity, while also providing some desirable redundancy in order to provide alternate route options and reduce congestion, or bottlenecking. One such network is described in a paper entitled xe2x80x9cSpine routing in ad hoc networksxe2x80x9d, R. Sivakumar, et al. Cluster Computing 1 (1998) p. 237-248 and may be characterized as an approximation to a xe2x80x9cMinimal Connected Dominating Setxe2x80x9d which is the smallest subset of a set of nodes in which all of the nodes of the subset are connected and can reach every node in the set via a single transmission, or hop.
Such networks advantageously reduce the bandwidth associated with updating routing tables. Further, since the backbone nodes have the greatest power requirements, minimizing the number of backbone nodes permits the nodes which may not have the necessary power capability to use the network. Additionally, both broadcast and multicast transmissions (i.e., single source with multiple receivers) are optimized since minimizing the backbone size minimizes replication of data at intermediate backbone nodes. However, care must be taken in providing a protocol for establishing and maintaining such networks in order to achieve these advantages while also providing a network capable of quickly and reliably adapting to a dynamically changing network.
It is an object of the present invention to provide a network protocol which is capable of rapidly adapting to network changes.
It is a further object to provide a network protocol which requires minimal bandwidth for establishing and maintaining the network.
Yet another object of the invention is to provide a network protocol which results in reliable communication between network nodes.
A still further object of the invention is to provide a network protocol which permits efficient multipoint-to-multipoint (multicast) communication among network nodes.
These and other objects of the invention are achieved by a method, or protocol for establishing a network from a plurality of nodes based on the periodic transmission and processing of signaling packets containing one or more protocol support records. The network includes a plurality of backbone nodes which are responsible for forwarding packets containing protocol records and other packets through the network (herein xe2x80x9ccategory black nodesxe2x80x9d) and a plurality of non-backbone nodes which are capable of reliably transmitting and receiving packets on the network, but which do not forward packets to other nodes (herein xe2x80x9ccategory green nodesxe2x80x9d). A third category of nodes (herein xe2x80x9ccategory white nodesxe2x80x9d) implement the protocol of the invention, but are not part of the network backbone and have not identified the existence of a reliable connection with a network backbone node.
Protocol support records include the Transmitter Status Record, Next Hop Information Record, Route Update Record, Address Resolution Notification Record, Address Resolution Query/Response Record, Route Query/Response Record, Multicast Join/Leave Record. The Transmitter Status and Next Hop Information Records are not forwarded through the network (i.e., they support xe2x80x98localxe2x80x99 (one hop) protocol information exchange). All other record types are forwarded through the network backbone.
To support the network protocol and routing methods, each node maintains a Node Information Table (herein xe2x80x9cNITxe2x80x9d) in which it stores and maintains basic information about other nodes in the network. For each listed node, such information includes, for example, the node""s MAC address and a deletion time stamp. Each node""s NIT entry also contains pointers to three other protocol tablesxe2x80x94the Route Table, the Neighbor Status Table, and the Protocol Support Record Queue. A node""s Route Table entry contains primary and secondary routes to reach it, with respect to a plurality of Quality of Service (QoS) routing metrics (i.e., such as bandwidth and delay). Routes are represented by the xe2x80x9cnext hop addressxe2x80x9d (gateway node) through which the node can be reached and the level of QoS that the route is capable of supporting. The Route Table also contains received quality information that represents the regularity and estimated rate with which route updates are being received from the destination. The Neighbor Status Table contains status information about neighbor nodes contained in received Transmitter Status Records. Status information includes, for example, category designation (herein xe2x80x9ccolorxe2x80x9d), backbone capability, non-category black neighbor count (herein xe2x80x9cdegreexe2x80x9d), category black neighbor count (herein xe2x80x9cblack degreexe2x80x9d), receive link quality data, transmit link quality data (obtained from the node""s Next Hop Information Record), and a sequence number counter which supports a CONNECTION process.
Network backbone creation begins with a SELECTION process which is performed only by white nodes. SELECTION is responsible for identifying an initial set of network backbone nodes (i.e., it xe2x80x9cseedsxe2x80x9d the network with black nodes). In general, a category white node is selected to become a backbone node as a result of having more non-backbone neighbors than any of its neighboring nodes.
An EXPANSION process is also performed by category white nodes and, in particular, by category white nodes that do not pass the SELECTION process. EXPANSION is the process by which a white node xe2x80x98asksxe2x80x99 a green neighbor to become a network backbone node (via the Next Hop Information Record""s next hop address and next hop control fields). This will cause the category white node to become category green, since it now has a category black neighbor. Collectively, the SELECTION and EXPANSION processes result in a network consisting of green and black nodes with varying degrees of backbone connectivity (i.e., the set of black nodes may or may not be fully connected).
CONNECTION is the process by which disconnected backbone segments become fully connected. Category green nodes determine whether or not they span disconnected backbone segments based on redundant Route Update Record receptions. To detect disjoint backbone segments, each green node selects one of its black neighbors as its Connection Test Point (CTP). Since the backbone""s responsibility is to forward Route Update Records (RURs), it follows that a green node can expect to hear its neighbors"" RURs twicexe2x80x94once from the neighbor""s original transmission and once from its CTP. If a category green node hears a neighbor""s RUR directly but does not hear the RUR forwarded by its CTP, it can be concluded that the neighbor is disconnected from the backbone segment represented by its CTP. A green node monitors both category green and category black neighbors, which represent the two basic types of CONNECTION processes. If the neighbor is a black node, then a black-green-black (B-G-B) disconnect condition has been detected since the green node is connecting a black neighbor with its CTP. For B-G-B disconnections, the category green node simply transitions to category black, thereby connecting the two disconnected category black nodes. If the neighbor is a category green node, a B-G-G-B disconnect condition has been detected since the green node is connecting its green neighbor""s CTP to its own CTP. For B-G-G-B disconnections, the green node and its green neighbor transition to category black (using a two way exchange of Next Hop Information Records containing each other""s address and the appropriate next hop control field setting).
The network backbone is maintained using the protocol""s MAINTENANCE process. As RURs are forwarded through the network backbone, nodes update their Route Tables. This process effectively yields a list of next hop addresses (herein xe2x80x9cgatewaysxe2x80x9d) that represent valuable routing alternatives. The Next Hop Information Record""s next hop address and next hop control fields are used to advertise gateways. A backbone node expects to hear itself advertised by at least one of its neighbors within a nominal period of time (herein xe2x80x9cgateway timeoutxe2x80x9d). If a backbone node does not hear itself advertised as a gateway within this period, it will either: (a) transition to category green if it has at least one category black neighbor; or (b) transition to category white if it does not have at least one black neighbor.
Efficient multicast routing is achieved over the established backbone by forwarding packets only to members of a multicast group rather than broadcasting packets to all nodes. Multicast trees (i.e., subsets of backbone nodes) are dynamically established and maintained based on the status of a Multicast Routing Table maintained by each backbone node and in response to Multicast Join and Leave Records.
All nodes generate signaling packets containing protocol support records at random intervals, between a specified maximum and minimum interval. The maximum and minimum intervals are selected according to the expected mobility of network nodes and predefined limits on bandwidth utilization for the purpose of protocol signaling. A node""s basic signaling packet contains, at a minimum, a Transmitter Status Record, a Next Hop Information Record, and a Route Update Record. The purpose of this basic signaling packet generation process is to support local node discovery and status dissemination, as well as inject the node""s own Route Update Record into the network.
Backbone nodes also generate and transmit signaling packets for the purpose of forwarding multi-hop records and providing local feedback to neighbor nodes. From a system perspective, bandwidth utilization for this function must be limited to acceptable levels. In particular, category black nodes track the rate at which records are inserted into the Protocol Support Record Queue. This rate is translated into a signaling packet generation rate that would effectively empty the queue as fast as it is filled. If bandwidth utilization levels allow, a black node generates signaling packets as fast as is necessary to maintain an empty record queue. If however, system bandwidth utilization dictates a decrease in the signaling packet generation rate; then a black node will accordingly to decrease its signaling packet generation rate and discard records that have expired or are lower priority (queue overflow).
Use of the described signaling packets for establishing and maintaining a wireless ad hoc network advantageously provides a simple technique for dynamically modifying the network based on mobility of nodes and minimizes the bandwidth necessary for such functions. This is because (1) the signaling packets are small in size (tens of bytes) due to their xe2x80x9crecord-basedxe2x80x9d structure, as opposed to the use of xe2x80x9cfixed formatxe2x80x9d packets designed to provide complete update information whether or not it is necessary; (2) signaling packets are forwarded only by backbone nodes rather than, for example, being broadcast by all network nodes (xe2x80x9cfloodingxe2x80x9d); (3) protocol support records support explicit functionality and can, therefore, be prioritized and selectively purged to accommodate fluctuations in available bandwidth; and (4) signaling packets are generated at predetermined, periodic rates, thereby resulting in node status and routing information being continuously updated and in continuous and rapid adaptation to network changes (i.e., as contrasted to disseminating such information only after a change is detected).
A key aspect of the invention is multi-hop link quality inference. Neighbor interaction that controls backbone creation and maintenance does not take place unless the neighbors have verified acceptable link quality (a system specific definition). With this knowledge, local exchange of link quality information is enough to support multi-hop route verification (i.e., a node knows that it only receives RURs over routes whose links pass the same quality test as its link with the gateway delivering the RUR). Receive link quality monitoring is supported by the Transmitter Status Record""s transmitter address and sequence number. The Next Hop Information Record""s next hop address and link quality (LQ) fields support the exchange of receive link quality values, which provides two-way link quality information for a node.